Поиск в графе

Поиск в ширину

Одним из наиболее часто используемых алгоритмов на графах является "Алгоритм поиска в ширину" или "волновой алгоритм". Основное его назначение - это поиск кратчайшего пути между двумя вершинами в не взвешенном графе. Например следующая задача: дан граф (рис1) надо найти такой путь между 1-ой и 10-ой вершиной, который проходил бы через минимальное количество вершин. Найти его длину и вывести его самого.
рис.1
Как мы ее будем решать? Тут то и понадобится алгоритм поиска в ширину. Сформулируем его:

1-ый этап. Мы отмечаем все вершины, которые находятся на расстоянии одного шага от начальной (в этом примере 1-ой) вершины. Мы заводим массив, в котором в i-ой ячейке будет записано расстояние от начальной вершины до i-ой. Назовем этот массив H. Тогда во все ячейки этого массива, которые соответствуют вершинам, находящимся на расстоянии одного шага от 1-ой, запишем 1. А в саму начальную 0.
Номер вершины (i)12345678910
H[i]01111-----
2-ой этап. Отмечаем все вершины, находящиеся на расстоянии 2-х ребер от начальной. Для этого просматриваем все вершины, до которых расстояние равно одному шагу. Для каждой из них отмечаем все смежные с ней и одновременно не отмеченные ранее вершины (т.к. раз они уже отмечены, то до них можно добраться быстрее) и записываем в ячейки массива Н, соответствующие им, 2.
Номер вершины (i)12345678910
H[i]01111222--
и так далее
i-ый этап. Отмечаем все вершины, находящиеся на расстоянии i ребер от данной. Для этого просматриваем все вершины, до которых расстояние равно i-1 шагов. Для каждой из них отмечаем все смежные с ней и одновременно не отмеченные ранее вершины и записываем в ячейки массива Н, соответствующие им, i.
Алгоритм продолжает работу до тех пор, пока мы не отметим ту вершину, путь до которой нам нужно найти (в примере 10-ая). Итоговое значение массива Н:
Номер вершины (i)12345678910
H[i]0111122233
Примечание: знак "-" означает, что вершина еще не просмотрена. Его можно заменить, например числом -1, тогда чтобы, рассматривая вершину i, отметить вершину j, надо, чтобы выполнялось следующее условие (где d - матрица смежности и d[i,j]=1, если есть дуга из i в j ):
if (d[i,j] = 1) and (H[j]=-1) then{...}

Теперь мы знаем, что расстояние от 1-ой вершины до 10-ой равно трем ребрам.
Рассмотрим временную сложность данного алгоритма. Если на каждом i-ом этапе для поиска вершин, находящихся на расстоянии i ребер от начальной мы будем просматривать все вершины, то мы просмотрим N вершин. Для каждой из них просмотрим N вершин, для проверки, смежная ли она с текущей. То получается, что на каждом этапе мы делаем N2 операций, а ведь этапов может быть максимум М(количество ребер в графе), если граф - цепь, и значит сложность алгоритма M*N2. Как же повысить эффективность алгоритма? Для этого используем структуру данных, называемую очередью.

Очередь
Очередь - структура данных, обладающая следующими свойствами:
1)Элементы можно добавлять только в конец очереди.
1)Брать элементы можно только из начала очереди. После того как элемент взят, он удаляется.
Как ее можно организовать? Чаще всего используется следующая схема:
Заводится массив, назовем его Turn. И два маркера (Переменные целого типа, отмечающие какие либо ячейки массива), назовем их b и e. Маркер b будет указывать на начало очереди, т.е. на первый элемент в очереди. А маркер e будет указывать на конец очереди, т.е. на первый пустой элемент, после конца очереди. Таким образом, чтобы считать элемент из очереди, необходимо лишь считать элемент Turn[b], и увеличить значение b на 1. Тогда элемент, который раньше был под номером b, уже не будет находится внутри очереди.
Чтобы добавить элемент в очередь, достаточно занести нужное значение в ячейку очереди с номером e, т.е. в Turn[e] и увеличить значение e на 1, чтобы он опять указывал на первый пустой элемент.
Так как в каждый момент времени используется не весь массив, а только небольшая его часть, то часто применяют циклическую очередь. Это означает, что после последнего элемента массива идет первый. На практике это значит, что если перед тем как увеличить значение маркера (b или e) он указывал на последний элемент в массиве, то вместо того, чтобы увеличить его значение на 1, ему надо присвоить 1. Чтобы пояснить цикличность очереди, покажем ее на рисунках. Следующие очереди эквивалентны, т.к. в них одинаковое количество элементов и их значения так же совпадают.

Приведем текст части программы на Паскале, добавляющей элемент Х в очередь. Причем максимальное количество элементов в очереди хранится в константе MaxTurn:
Turn[e]:=X;
e:=e+1;
if MaxTurn<e then e:=1;
Теперь текст части программы на Паскале, которая извлекает из очереди элемент и помещает его значение в переменную Х:
X:=Turn[b];
b:=b+1;
if MaxTurn<b then b:=1;
Примечание: Очередь считается пустой, когда b=e, т.к. в этом случае первый элемент очереди и первый пустой элемент после конца очереди совпадают.

Как мы можем применить очередь в нашей задаче? Мы не будем на каждом этапе пробегать все вершины. Каждый, раз отмечая вершину, будем помещать ее в очередь. А когда мы будем просматривать очередную вершину, мы будем брать ее из очереди. Таким обозом мы потихоньку рассмотрим сначала все вершины, находящиеся на расстоянии 1-го ребра от начальной, потом на расстоянии 2-х и так далее. Причем в самом начале мы должны поместить в очередь начальную вершину.
Мы должны продолжать работу до тех пор, пока мы не отметим вершину, до которой нам надо добраться, или пока очередь не станет пустой (в случае если пути до этой вершины не существует)
Как выбрать константу MaxTurn? Одновременно в очереди могут находится элементы, принадлежащие только двум уровням. Действительно, просматривая очередной элемент, мы можем добавить элемент только следующего уровня, а предыдущий уже удален. Под словом уровень, подразумевается расстояние от начальной вершины до данной; элементы одного уровня находятся на одинаковом расстоянии от начальной вершины. Значит MaxTurn - это сумма двух максимальных по количеству уровней (волн).

Оценим теперь временную сложность алгоритма. В каждой вершине мы бываем ровно один раз, и для каждой вершины мы проверяем все N вершин, не являются ли они смежными с текущей, т.е. мы делаем N2 операций. Но это в случае, если мы храним граф матрицей смежности. А если мы храним граф списком ребер, то алгоритм заключается в просмотре ребер, а значит по каждому ребру мы один раз двигаемся вперед ( на шаг вперед) и один раз пытаемся сходить назад, а значит мы делаем 2*M действий (где M - количество ребер).

Итог: временная сложность алгоритма O(M), где M - количество ребер.

Но мы не решили полностью задачу. Нам еще надо вывести путь. Для этого мы заведем массив, в i-ой ячейке которого будет хранится, из какой вершины мы пришли в нее, назовем его Last. Тогда на каждом шаге поиска в ширину, мы отмечая очередную вершину будем записывать, в соответствующую ей ячейку массива Last номер текущей вершины. То есть если мы находимся в вершине i и хотим отметить вершину j, то мы заносим в Last[i] значение j . ( Last[i]:=j ). Для нашего примера значение массива Last будет следующим:
Номер вершины (i)12345678910
Last[i]0111124378
Теперь чтобы вывести путь надо, находясь сначала в конечной вершине (В примере номер 10), отметим ее маркером i, вывести первым его значение, а потом перейти на ячейку с номером Last[i], т.е. i:=Last[i]. Вывести и его значения. И так далее, пока i не станет равно начальной вершине. Результат:
10-8-3-1
Но тогда путь выведется в обратном порядке. Что делать? Одно из решений - завести массив, назовем его Way, и Записать в него путь, а потом вывести элементы этого массива в обратном порядке. Напишем пример программы, выводящий данный путь по сформированному массиву Last. Начальная вершина BegV, конечная EndV, длинна пути WayLen: 

i:=EndV; {Устанавливаем маркер i на последнюю вершину}
WayLen:=1; {Устанавливаем длину пути равную 1}
Way[1]:=i; {Записываем в путь первым элементов последнюю вершину}
while i<>BegV do begin {Пока не доберемся до начальной вершины}
  i:=Last[i]; {Переходим к предыдущей}
  inc(WayLen); {Увеличиваем длину пути}
  Way[WayLen]:=i; {Записываем очередную вершину в путь}
end;
for i:=WayLen downto 1 do {Выводим путь задом на перед (В естественном порядке)}
  write(Way[i],' ');

Проведем еще одну оптимизацию нашего алгоритма, но уже по памяти. Если вы заметили, то в процессе нахождении пути, мы также и находим его длину. Если нам не надо находить длину пути отдельно от самого пути, то мы можем обойтись лишь массивом Last. Мы сначала заполним его числами -1, а в начальную вершину запишем 0. Тогда, чтобы проверить не просмотрена ли j-ая вершина, мы должны проверить ячейку Last[j] на равенство с -1. Если там записано что-нибудь другое, то эту вершину уже просматривали, мы записывали в Last[j] его предыдущую вершину. Пример условия (где d - матрица смежности и d[i,j]=1, если есть дуга из i в j ):
if (d[i,j] = 1) and (Last[j]=-1) then{...}
Примечание: Если нам надо находить расстояние до вершин, до которых не надо находить путь, то такая оптимизация не целесообразна.

Задача о поиске выхода из лабиринта.

Формулировка задачи: Человек оказался в лабиринте, который задается картой, представляющей собой матрицу NхM, в которая состоит из 0 и 1, где 1 означает что в этой ячейке скала и в нее шагать нельзя, а 0, что нет скалы и шагать можно. Причем из каждой ячейки можно шагать только в те, что имеют смежную сторону с данной. Даются координаты человека Xb и Yb. Выходом считаются все крайние ячейки матрицы. Найти длину пути. Если пути нет, то вывести -1

Чаще всего эта задача также решается с помощью поиска в ширину. Мы рассмотрим матрицу как граф, вершинами которого будут нулевые ячейки. Две вершины связаны ребром, если они имеют смежную сторону.
Как хранить этот граф? Матрицей смежности? Но тогда вершин N*M, а матрица смежности получится N2*M2.Если M и N хотя бы 100, а на каждую ячейку тратится по байту, то матрица будет занимать 1000000 байт. А такого количества памяти у нас нет. Что мы будем делать? Мы не будем держать матрицу смежности, ведь по координатам ячейки мы можем сразу вычислить координаты ее соседей. Например: у ячейки с координатами (i,j) соседями являются ячейки с координатами (i-1,j),(i+1,j),(i,j-1) и (i,j+1), если конечно там не скалы. И так мы заведем одну матрицу, назовем ее Map. И поместим туда карту. Но вместо того, чтобы писать 1 будем писать -1. Теперь запускаем волну(поиск в ширину) из ячейки с координатами (Xb,Yb). Алгоритм будет работать до тех пор, пока не будет отмечена ячейка у которой x=1, x=M, y=1 или y=N, или пока очередь не станет пустой(тогда выхода из лабиринта нет!).
Оформим наш алгоритм на Паскале (т.к. ячейка задается двумя координатами, то очередь у нас будет состоять из двух векторов. Заведем переменную Find булевского типа, которая будет true, если мы нашли выход, и false, если еще нет): 

b:=1; {Устанавливаем начало очереди в первом элементе}
e:=2; {А первый после конца, это второй элемент (т.е. очередь состоит из одного элемента)}
Turn[1,1]:=Xb; {Заносим координату Х первого элемента очереди}
Turn[1,2]:=Yb; {Заносим координату Y первого элемента очереди}
Find:=false; {Отмечаем, что выход еще не найден}
while (b <> e) and not find do begin
  {Работаем, пока очередь не станет пустой или не найдется выход}
  wave(Turn[b,1],Turn[b,2]); {Обработка вершины}
  b:=b+1; {Переход к следующему элементу очереди}
  if b>MaxTurn then b:=1; {Цикличность очереди}
end;
if not find then write(-1); {Если путь не найден, то выводим об этом сообщение}
В этой части программы есть процедура wave, которая обрабатывает вершину, выпишем ее: 
procedure wave(x,y:integer);
{Процедура обрабатывает ячейку, находящуюся в y-ой строке и x-ом столбце}
  var i:integer;
  begin
    for i:=1 to 4 do {Просматриваем 4-х соседей}
      if Map[y+dy[i],x+dx[i]]=0 then begin {Если там пусто и она не отмечена}
        Map[y+dy[i],x+dx[i]]:=Map[y,x]+1; {Записываем, что это вершина следующего уровня}
        Turn[e,1]:=x+dx[i];
        Turn[e,2]:=y+dy[i]; {Заносим этого соседа в очередь}
        e:=e+1;
        if e>MaxTurn then e:=1; {Цикличность очереди}
        if (x+dx[i]=1)or(x+dx[i]=m)or(y+dy[i]=1)or(y+dy[i]=n) then begin
          {Если этот сосед - выход}
          write(Map[y+dy[i],x+dx[i]); {Выводим расстояние до выхода}
          find:=true; {Отмечаем, что он найден}
          break; {Останавливаем поиск соседей}
        end;
      end;
  end;
Чтобы не расписывать, что соседи (i,j)-ячейки - ячейки с номерами (i-1,j),(i+1,j),(i,j-1) и (i,j+1), мы заводим два массива констант dx и dy, описываемые следующем образом в разделе констант: 
const dx:array[1..4]of integer = (1,-1,0,0);
      dy:array[1..4]of integer = (0,0,-1,1);
Сайт управляется системой uCoz